package 拓扑排序;

import java.util.ArrayList;
import java.util.List;

public class Course {
    static List<List<Integer>> edges;
    static int[] visited;
    static boolean valid = true;

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        edges=new ArrayList<>();
        visited=new int[numCourses];
        for (int i=0;i<numCourses;++i){
            edges.add(new ArrayList<>());
        }
//        创建邻接表
        for (int[] course:prerequisites){
            edges.get(course[1]).add(course[0]);
        }
//        创建visited数组
        for (int i=0;i<numCourses;++i){
            visited[i]=0;
        }
        for (int i=0;i<numCourses;++i){
            if(visited[i]==0){
                dfs(i);
                if(!valid){
                    return false;
                }
            }
        }
        return true;
    }

    public static void dfs(int u) {
//        访问过的顶点置为1
        visited[u]=1;
//        获取邻接顶点
        /**
         * 思考：为什么要置为2
         *      置为2说明在当前路径中所有的节点是符合要求的，不存在环
         */
        List<Integer> next = edges.get(u);
        for (int v:next){
            if(visited[v]==0){
                dfs(v);
            } else if(visited[v]==1){
                valid=false;
                return;
            }
        }
//        表示当前节点符合要求
        visited[u]=2;
    }

    public static void main(String[] args) {
        System.out.println(canFinish(6,new int[][]{{3,0},{3,1},{4,1},{4,2},{5,3},{5,4}}));
    }
}

